﻿using System.Text;

namespace DataStructure;

//三元组十字链表矩阵类
public class TOMatrix<E> : ITMatrix<E> where E : struct
{
    private class Triple //三元组类型
    {
        public int r; //行号
        public int c; //列号 
        public E e;   //元素值
    }

    private class TripOrtho //三元组十字链表
    {
        public CirLinkList<Triple> right; //三元组行链表
        public CirLinkList<Triple> down;  //三元组列链表
    }

    private CirLinkList<TripOrtho> h; //十字表头链表

    public int Rows { get; } //稀疏矩阵的行数
    public int Cols { get; } //稀疏矩阵的列数
    private int Max;         //稀疏矩阵的行列数最大值
    public int Nums { get; set; } //十字表三元组（非0元）个数

    public TOMatrix(int Rows, int Cols, int Nums)
    {
        this.Rows = Rows;
        this.Cols = Cols;
        this.Nums = Nums;
        Max = Math.Max(Rows, Cols);

        h = new CirLinkList<TripOrtho>(); //创建十字表头链表
        for (int k = 0; k < Max; k++) //十字表头链表初始化
        {
            TripOrtho head = new TripOrtho();
            head.right = new CirLinkList<Triple>(); //创建行链表
            head.down = new CirLinkList<Triple>();  //创建列链表

            h.AddLast(head);
        }
    }

    public TOMatrix(E[,] a) //创建a的十字链表
    {
        Rows = a.GetLength(0);
        Cols = a.GetLength(1);
        Max = Math.Max(Rows, Cols);

        h = new CirLinkList<TripOrtho>(); //十字表头链表初始化
        for (int k = 0; k < Max; k++)
        {
            TripOrtho head = new TripOrtho();
            head.right = new CirLinkList<Triple>();
            head.down = new CirLinkList<Triple>();

            h.AddLast(head);
        }

        //按行序方式扫描所有元素
        for (int i = 0; i < Rows; i++) //处理每一行
        {
            for (int j = 0; j < Cols; j++) //处理每一列
            {
                if (!a[i, j].Equals(default(E))) ////处理非零元素
                {
                    Triple triple = new Triple  //创建一个新结点
                    {
                        r = i,
                        c = j,
                        e = a[i, j]
                    };

                    h[i].right.AddLast(triple);
                    h[j].down.AddLast(triple);

                    Nums++;
                }
            }
        }
    }

    public TOMatrix(string file)
    {
        StreamReader sr = new StreamReader(file);

        string line = sr.ReadLine();
        string[] str = line.Split(' ');

        Rows = int.Parse(str[0]);
        Cols = int.Parse(str[1]);
        Max = Math.Max(Rows, Cols);
        Nums = int.Parse(str[2]);

        h = new CirLinkList<TripOrtho>(); //十字表头链表初始化
        for (int k = 0; k < Max; k++)
        {
            TripOrtho head = new TripOrtho();
            head.right = new CirLinkList<Triple>();
            head.down = new CirLinkList<Triple>();

            h.AddLast(head);
        }

        for (int i = 0; i < Nums; i++)
        {
            line = sr.ReadLine();
            str = line.Split(' ');

            Triple triple = new Triple
            {
                r = int.Parse(str[0]),
                c = int.Parse(str[1]),
                e = (E)Convert.ChangeType(str[2], typeof(E))
            };

            h[triple.r].right.AddLast(triple);
            h[triple.c].down.AddLast(triple);
        }

        sr.Close();
    }

    public E[,] SparseMatrix()
    {
        E[,] sparseMatrix = new E[Rows, Cols];

        for (int k = 0; k < h.Count; k++)
        {
            CirLinkList<Triple> right = h[k].right;

            for (int s = 0; s < right.Count; s++)
            {
                sparseMatrix[right[s].r, right[s].c] = right[s].e;
            }
        }

        return sparseMatrix;
    }

    private bool GetByCoord(int i, int j, out Triple triple)
    {
        triple = null;

        if (i < 0 || i >= Rows || j < 0 || j >= Cols)
        {
            return false; //索引越界，操作失败，返回false。
        }

        CirLinkList<Triple> right = h[i].right;
        for (int s = 0; s < right.Count; s++)
        {
            if (right[s].c == j)
            {
                triple = right[s];
            }
            return true;
        }

        return true;
    }

    public bool Assign(int i, int j, out E assignedE)
    {
        assignedE = default;

        bool res = GetByCoord(i, j, out Triple triple);
        if (!res)
        {
            return false;
        }

        if (triple is not null)
        {
            assignedE = triple.e;
        }

        return true;
    }

    public bool Amend(int i, int j, E newE)
    {
        bool res = GetByCoord(i, j, out Triple triple);
        if (!res)
        {
            return false;
        }

        if (triple is not null) //表中存在此元素
        {
            if (newE.Equals(default(E)))    //如果给该元素赋值为0
            {
                h[i].right.Remove(triple); //将该元素从表中删除。
                Nums--;                    //表元素个数减一
            }
            else                           //如果给该元素赋值为非0    
            {
                triple.e = newE;  //将表中该元素修改为另一个不为0的新值
            }

            return true; //修改完毕，操作成功，返回真
        }

        //表中不存在此元素
        if (newE.Equals(default(E))) //如果给该元素赋值为0
        {
            return true;  //表无变化，元素仍是零值，操作无碍，返回真。        
        }

        //如果给该元素赋值为非0，往表中插入 
        Triple newTriple = new Triple  //创建新的三元组
        {
            r = i,
            c = j,
            e = newE,
        };

        CirLinkList<Triple> right = h[i].right;
        int s = 0;
        while (s < right.Count && right[s].c < j)
        {
            s++;
        }
        right.Add(s, newTriple);

        CirLinkList<Triple> down = h[j].down;
        int t = 0;
        while (t < down.Count && down[t].r < i)
        {
            t++;
        }
        down.Add(t, newTriple);

        return true; //插入成功，返回真值        
    }

    public TOMatrix<E> Transpose()
    {
        TOMatrix<E> transMat = new TOMatrix<E>(Cols, Rows, Nums); //定义转置后的矩阵

        if (Nums != 0) //非零矩阵转置
        {
            for (int k = 0; k < Max; k++)
            {
                CirLinkList<Triple> right = h[k].right, down = h[k].down;

                for (int s = 0; s < right.Count; s++)
                {
                    Triple triple = new Triple
                    {
                        r = right[s].c,
                        c = right[s].r,
                        e = right[s].e,
                    };

                    transMat.h[k].down.AddLast(triple);
                }

                for (int s = 0; s < down.Count; s++)
                {
                    Triple triple = new Triple
                    {
                        r = down[s].c,
                        c = down[s].r,
                        e = down[s].e,
                    };

                    transMat.h[k].right.AddLast(triple);
                }
            }
        }

        return transMat;
    }

    public TOMatrix<E> Add(TOMatrix<E> other)
    {
        if (Rows != other.Rows || Cols != other.Cols)
        {
            throw new InvalidOperationException("两矩阵的行数或列数不等，不能相加！");
        }

        TOMatrix<E> res = new TOMatrix<E>(Rows, Cols, 0);

        for (int k = 0; k < Max; k++)
        {
            CirLinkList<Triple> right = h[k].right, rightOther = other.h[k].right;

            int s = 0, sOther = 0;
            while (s < right.Count && sOther < rightOther.Count)
            {
                while (s < right.Count && sOther < rightOther.Count && right[s].c < rightOther[sOther].c)
                {
                    res.h[k].right.AddLast(right[s]);
                    res.h[right[s].c].down.AddLast(right[s]);

                    s++;
                    res.Nums++;
                }

                while (s < right.Count && sOther < rightOther.Count && right[s].c > rightOther[sOther].c)
                {
                    res.h[k].right.AddLast(rightOther[s]);
                    res.h[rightOther[s].c].down.AddLast(rightOther[s]);

                    sOther++;
                    res.Nums++;
                }

                while (s < right.Count && sOther < rightOther.Count && right[s].c == rightOther[sOther].c)
                {
                    dynamic e = right[s].e;
                    dynamic eOther = rightOther[sOther].e;

                    res.Amend(right[s].r, right[s].c, e + eOther);

                    s++;
                    sOther++;
                }
            }

            while (s < right.Count)
            {
                res.h[k].right.AddLast(right[s]);
                res.h[right[s].c].down.AddLast(right[s]);

                s++;
                res.Nums++;
            }

            while (sOther < rightOther.Count)
            {
                res.h[k].right.AddLast(rightOther[s]);
                res.h[rightOther[s].c].down.AddLast(rightOther[s]);

                sOther++;
                res.Nums++;
            }
        }

        return res;
    }

    public TOMatrix<E> Sub(TOMatrix<E> other)
    {
        return Add(-other);
    }

    public static TOMatrix<E> operator +(TOMatrix<E> X, TOMatrix<E> Y)
    {
        return X.Add(Y);
    }

    public static TOMatrix<E> operator -(TOMatrix<E> X, TOMatrix<E> Y)
    {
        return X.Add(-Y);
    }

    public static TOMatrix<E> operator -(TOMatrix<E> X)
    {
        TOMatrix<E> res = new TOMatrix<E>(X.Rows, X.Cols, X.Nums);

        for (int k = 0; k < X.Max; k++)
        {
            CirLinkList<Triple> right = X.h[k].right;
            for (int s = 0; s < right.Count; s++)
            {
                dynamic temE = right[s].e;
                Triple triple = new Triple
                {
                    r = right[s].r,
                    c = right[s].c,
                    e = -temE,
                };

                res.h[k].right.AddLast(triple);
                res.h[s].down.AddLast(triple);
            }
        }

        return res;
    }

    public void Clear()
    {
        h = null;
        Nums = 0;
    }

    public override string ToString() //输出十字链表
    {
        if (Nums <= 0)
        {
            return string.Empty;
        }

        StringBuilder sb = new StringBuilder();

        sb.AppendLine($"\t{Rows}\t{Cols}\t{Nums}");
        sb.AppendLine("\t-------------------");

        for (int k = 0; k < Max; k++)
        {
            CirLinkList<Triple> right = h[k].right;

            for (int s = 0; s < right.Count; s++)
            {
                sb.AppendLine($"\t{right[s].r}\t{right[s].c}\t{right[s].e}");
            }
        }

        return sb.ToString();
    }
}

class TOMatrix
{
    static void Main(string[] args)
    {
        int[,] sparseMatrix = //6*7
       {
            {0, 0, 1, 0, 0, 0, 0,},
            {0, 2, 0, 0, 0, 0, 0,},
            {3, 0, 0, 0, 0, 0, 0,},
            {0, 0, 0, 5, 0, 0, 0,},
            {0, 0, 0, 0, 6, 0, 0,},
            {0, 0, 0, 0, 0, 7, 4,},

        };

        TOMatrix<int> tOMatrixA = new TOMatrix<int>(sparseMatrix);
        Console.WriteLine(tOMatrixA);
        tOMatrixA.SparseMatrix().Print();

        TOMatrix<int> tOMatrixB = new TOMatrix<int>("三元组/三元组.txt");
        tOMatrixB.Assign(5, 5, out int a);
        Console.WriteLine(a);
        Console.WriteLine(tOMatrixB.Transpose());

        TOMatrix<int> tOMatrix1 = new TOMatrix<int>("三元组/三元组2.txt");
        TOMatrix<int> tOMatrix2 = new TOMatrix<int>("三元组/三元组3.txt");

        TOMatrix<int> tOMatrix3 = tOMatrix1 + tOMatrix2;
        TOMatrix<int> tOMatrix4 = tOMatrix1 - tOMatrix2;

        Console.WriteLine(tOMatrix3);
        Console.WriteLine(tOMatrix4);
    }
}


